In recent years, object-oriented programming has become the standard programming paradigm. In object oriented programming, the world is modeled in terms of objects. An object is a record combined with the procedures and functions that manipulate it.
The behavior of objects is specified by classes, which are like "data types" of traditional programming languages, but serve additionally to classify objects into hierarchies through an inheritance mechanism, as described in such languages as the Java.TM. programming language. The classes serve as templates from which objects can be created. All objects in a class have the same fields ("attributes"), and are manipulated by the same procedures and functions ("methods"). An object is said to be an "instance" of the class to which it belongs.
The attributes of an object may themselves be objects, and therefore belong to their own classes. Under various circumstances, it is desirable to have objects that differ from each other only in the classes to which their attributes belong. For example, it may be necessary for a particular application to have a vector of strings, a vector of characters, and a vector of vectors of strings. In each of these cases, the vectors differ only in the type of elements stored in the vectors.
One solution is to define a separate class definition for each of the attribute types. For example, a vector class can be defined for vectors having attributes belonging to the class of Characters, another vector class can be defined for vectors having attributes belonging to the class of Strings, and still another vector class can be defined for vectors having attributes belonging to the class of Vectors of Strings.
The following code example uses the Java.TM. programming language to define a type-specific Vector class having attributes belonging to the class of Character.
______________________________________ TYPE-SPECIFIC CLASS ______________________________________ 10 class CharacterVector { 12 public static final int CAPACITY = 4; 14 private Character [] oa = new Character[CAPACITY]; 18 public Character get (int i) { 20 if(0 &lt;= i && i &lt; CAPACITY) return oa[i]; 22 else throw new IndexOutOfBoundsException(); 24 } 26 public void set (int i, Character val) { 28 if(0 &lt;= i && i &lt; CAPACITY) oa[i] = val; 30 else throw new IndexOutOfBoundsException(); 32 } 34 } ______________________________________
In this example, the class Vector includes two attributes (CAPACITY and oa) and two methods (get and set). The oa attribute is defined at line 14 as an array of elements that are of type "Character". The CAPACITY attribute is an int constant that defines the minimum storage capacity of the array oa. In the example, the array oa is initially allocated to store no less than four elements (Characters).
The get method, defined in lines 18-24, is called to get the ith element from the oa vector. The get method takes an input parameter "i" that is of type int and returns a value that is of type Character. At line 20, if the index value "i" is within range, the Character at location "i" of array oa is returned. The set method, defined in lines 26-32, takes input parameter "i" that is of type int and input parameter val that is of type Character. The set method is called to set the ith element in the oa vector to the Character as defined by the parameter val. In both methods, if the index value "i" is not within range, an out-of-bounds exception is thrown (IndexOutOfBoundsException).
Alternatively, a type-specific Vector class having attributes belonging to the class of String, can be defined using the Java programming language as follows:
______________________________________ TYPE-SPECIFIC CLASS ______________________________________ 40 class StringVector { 42 public static final int CAPACITY = 4; 44 private String [] oa = new String[CAPACITY]; 48 public String get (int i) { 50 if(0 &lt;= i && i &lt; CAPACITY) return oa[i]; 52 else throw new IndexOutOfBoundsException(); 54 } 56 public void set (int i, String val) { 58 if(0 &lt;= i && i &lt; CAPACITY) oa[i] = val; 60 else throw new IndexOutOfBoundsException(); 62 } 64 } ______________________________________
In this example, the class Vector includes two attributes (CAPACITY and oa) and two methods (get and set). The oa attribute is defined at line 44 as an array of elements that are of type "String". The CAPACITY attribute is an int constant that defines the minimum size of oa. In this example, oa will hold at least four elements (Strings).
The get method, defined in lines 48-54, is called to get the ith element from the oa vector. The get method takes an input parameter "i" that is of type int and return a value that is of type String. At line 50, if the index value "i" is within range, the String at location "i" of array oa is returned. The set method, defined in lines 56-62, takes input parameter "i" that is of type int and input parameter val that is of type String. The set method is called to set the ith element in the oa vector to the String as defined by the parameter val. In both methods, if the index value "i" is not within range, an out-of-bounds exception routine is called (IndexOutOfBoundsException).
A draw back of defining a type-specific class for each attribute type (i.e. Character, String, etc.), is that memory must be allocated for each type-specific class definition. Allocating space for each type-specific class is both wasteful and inefficient as memory is consumed by redundant code.
One approach to reducing the redundancy caused by the allocation of memory for each type-specific class definition is to have a class definition that is generic. A generic class definition specifies one or more attributes to be of the generic object class. Because all classes descend from the generic object class, the programmer is free to store type-specific classes as generic-type object classes. For example, a Vector class may be defined having attributes of type "Object". By defining the generic Vector class as having attributes of type Object, a single class definition can be used for processing multiple attribute types (i.e. Character, String, etc.).
The following code example, using the Java.TM. programming language, defines a generic Vector class having attributes that belong to the class of Object.
______________________________________ GENERIC-TYPE VECTOR CLASS (UNPARAMETERIZED) ______________________________________ 70 class Vector { 72 public static final int CAPACITY = 4; 74 private Object [] oa = new Object [CAPACITY]; 78 public Object get (int i) { 80 if(0 &lt;= i && i &lt; CAPACITY) return oa[i]; 82 else throw new IndexOutOfBoundsException(); 84 } 86 public void set (int i, Object val) { 88 if(0 &lt;= i && i &lt; CAPACITY) oa[i] = val; 90 else throw new IndexOutOfBoundsException(); 92 } 94 } ______________________________________
In this example, the class Vector includes two attributes (CAPACITY and oa) and two methods (get and set). The oa attribute is defined at line 74 as an array of elements that are of type "Object". The CAPACITY attribute, is an int constant that defines the minimum number of elements (Objects) for which space will be allocated in the array oa.
The get method, defined in lines 78-84, is called to get the ith element from the oa vector. The get method takes an input parameter "i" that is of type int and returns a value that is of type Object. At line 80, if the index value "i" is within range, the Object at location "i" of array oa is returned. The set method, defined in lines 86-92, takes input parameter "i" that is of type int and input parameter val that is of type Object. The set method is called to set the ith element in the oa vector to the Object as defined by the parameter val. In both methods, if the index value "i" is not within range, an out-of-bounds exception is thrown (IndexOutOfBoundsException).
Because the Vector definition specifies elements of a generic type (i.e. type Object), vectors having different attribute types (i.e. Character, String, etc.), can be instantiated from the single class definition.
For example, using the Vector class definition as defined above in lines 70-94, the following line of user program code may be used to instantiate a vector having attributes of type Object.
______________________________________ USER PROGRAM CODE (UNPARAMETERIZED) ______________________________________ 100 Vector iv = new Vector(); // CREATE A VECTOR OF OBJECTS ______________________________________
As depicted in line 100, when a new vector is needed, a vector of type object (iv) is instantiated by requesting a new vector (iv). Because the instantiated vector "iv" has elements of type Object, it may contain elements of any object class that is a descendant of type Object. Since type Object is the generic object class from which all other object types descend, the vector iv may contain elements of any object class (i.e. Character, String, etc.). Therefore, a single vector class definition having elements of type Object may be used to instantiate vectors having elements of different element types (i.e. Character, String, etc.). This provides for a reduction in memory allocation, since a single class definition may be used to implement vector objects that store numerous types of elements.
A draw back associated with defining a generic vector type in this manner is that the programmer is forced to keep track of the type of element that is stored in each vector, and must use an appropriate, explicit "cast" in extracting an element from a particular vector. A cast is a mechanism that is used to explicitly convert a less specific type to a more specific type (e.g. a variable of type "Object" to a variable of type Character). For example, using the Java.TM. programming language, a fragment of user program code that makes use of the vector class defined in lines 70-94, may be as follows:
______________________________________ UNPARAMETERIZED USER PROGRAM SOURCE CODE ______________________________________ 102 Vector cv = new Vector(); 104 cv.set(0, new Character (`a`)); 106 cv.set(1, new Character (`b`)); 108 Character c = (Character)cv.get(0); 110 Vector sv1 = new Vector(); 112 sv1.set(0, "zero"); 114 sv1.set(1, "one"); 116 String s = (String)sv1.get(0); 118 Vector sv2 = new Vector(); 120 sv2.set(0, "one"); 122 String s2 = (String)sv2.get(0); 124 Character i2 = (Character)sv1.get(0); // RUN.sub.-- TIME ______________________________________ ERROR
The execution of this user program code example provides the following results. At lines 102, 110 and 118, vectors having attributes of type Object are instantiated as vectors cv, sv1 and sv2 respectively. At line 104 the element at location 0 of vector cv is set equal to the Character "a" and at line 106 the element at location 1 of vector cv is set equal to the Character "b". At line 108, a Character variable c is set equal to the element at location 0 in vector cv. As depicted, an appropriate cast must be used to explicitly convert from a less specific type to a more specific type (e.g. from a variable of type Object to a variable of type Character).
At line 112 the element at location 0 of vector sv1 is set equal to the String "zero" and at line 114 the element at location 1 of vector sv1 is set equal to the String "one". At line 116, a string variable s is set equal to the element at location 0 in vector sv1. Here again, an appropriate cast must be used to explicitly convert from a less specific type to a more specific type (e.g. from a variable of type Object to a variable of type String).
At line 120 the element at location 0 of vector sv2 is set equal to the String "one" and at line 122, a string variable s2 is set equal to the element at location 0 in vector sv2 using the appropriate cast.
As depicted in line 124, a drawback associated with using a generic-type vector class is that a run-time error occurs if an attempt is made to cast a vector element into an "incompatible" variable type (i.e. an attempt is made to cast a vector element of type String (element at location 0 of vector sv1) into a variable of type Character (c2)).
In certain languages, such as the Java.TM. programming language, the programmers themselves are required to insert the casts since the languages are statically type safe, thereby restricting the compiler from inserting appropriate casts at compile time. Thus, using a generic-type class as depicted in lines 70-94, a substantial burden is imposed on the programmer to correctly cast each element of type Object to its correct type in order to avoid introducing incompatible type assignment errors that typically cannot be caught at compile time. In addition, by requiring the use of casts, additional runtime overhead is introduced as the execution of type-casting instructions requires the use of extra computing cycles.
One approach to avoiding the substantial burden imposed on programmers by casting is through the use of parameterized classes. A parameterized class is a class in which the element type of the class is defined by a parameter. Class definitions that provide a type parameter list are referred to herein as parameterized classes. Because the type of parameter is specified in the code that uses the parameterized class, incompatible assignments and type casts can be detected at compile time in the context of the code that uses the parameterized class.
For example, a parameterized class alternative to the vector class definition previously described above (lines 70-94) may be defined as follows:
______________________________________ PARAMETERIZED CLASS LIBRARY SOURCE CODE ______________________________________ 130 class Vector&lt;A&gt;{ 132 public static final int CAPACITY = 4; 134 private A [] oa = new A [CAPACITY]; 138 public A get (int i) { 140 if(0 &lt;= i && i &lt; CAPACITY) return oa[i]; 142 else throw new IndexOutOfBoundsException(); 144 } 146 public void set (int i, A val) { 148 if(0 &lt;= i && i &lt; CAPACITY) oa[i] = val; 150 else throw new IndexOutOfBoundsException(); 152 } 154 } ______________________________________
In this example, the class Vector includes a parameter "A", two attributes (CAPACITY and oa) and two methods (get and set). The oa attribute is defined at line 134 as an array of elements that are of type "A". The CAPACITY attribute is an int constant that defines the number of elements (Objects) for which storage is allocated in the array oa.
The get method, defined in lines 138-144, is called to get the ith element from the oa vector. The get method takes an input parameter "i" that is of type int and returns a value that is of type A. At line 140, if the index value "i" is within range, the element at location "i" of array oa is returned. The set method, defined in lines 146-152, takes input parameter "i" that is of type int and input parameter val that is of type A. The set method is called to set the ith element in the oa vector to the parameter val, which has been defined as being of type A. In both methods, if the index value "i" is not within range, an out-of-bounds exception is thrown (IndexOutOfBoundsException).
By parameterizing the vector class definition, a single class definition can be used to instantiate vectors having elements of different attribute types (i.e. Character, String, etc.). In addition, by using a parameterized vector class definition, the type of element that is contained in each vector instance can be identified at compile time. This allows for static type-checking and the identification of incompatible type assignments during compilation, without the need of explicit type casts.
For example, using the Java.TM. programming language, the compilation of a fragment of user program code that is linked to the above parameterized vector class (lines 130-154), may be as follows.
______________________________________ PARAMETERIZED USER PROGRAM SOURCE CODE ______________________________________ 160 Vector&lt;Character&gt; cv = new Vector&lt;Character&gt; (); // CREATE VECTOR OF CHARACTERS 162 cv.set(0, `1`); 164 cv.set(2, `5`); 166 Character c = cv.get(0); // NO CAST REQUIRED 168 Vector&lt;String&gt; sv1 = new Vector&lt;String&gt; (); // CREATE 1.sup.st VECTOR OF STRINGS 170 sv1.set(0, "zero"); 172 sv1.set(1, "one"); 174 String s = sv1.get(0); // NO CAST REQUIRED 176 Vector &lt;String&gt; sv2 = new Vector &lt;String&gt; (); // CREATE 2.sup.nd VECTOR OF STRINGS 178 sv2.set(0, "one"); 180 String s2 = sv2.get(0); // NO CAST REQUIRED 182 Character c2 = sv1.get(0); // COMPILE-TIME ERROR ______________________________________
The execution of this parameterized class code example provides the following results. At line 160, a vector (cv) having elements of type Character is instantiated. Specifically, the "character" parameter passed when the vector constructor (the "new" method) is invoked in line 160 causes the creation of a new vector in which the attribute "oa" is an array of Character. Similarly, at lines 168 and 176 vectors (sv1 and sv2) having elements of type String are instantiated by invoking the vector constructor and passing "String" as the parameter value.
At line 162, the element at location 0 of vector cv is set equal to the Character "1" and at line 164 the element at location 2 of vector cv is set equal to the Character "5". At line 166, a Character variable c is set equal to the element at location 0 in vector cv. Because vector cv was previously instantiated as having attributes of type Character (line 160), the compiler is able to determine whether vector cv contains attributes that are compatible with the Character variable c. Therefore, a cast instruction is no longer required to explicitly convert from a less specific type to a more specific type.
At line 170, the element at location 0 of vector sv1 is set equal to the String "zero" and at line 172, the element at location 1 of vector sv1 is set equal to the String "one". At line 174, the element at location 0 in vector sv1 is assigned to a String variable s. Here again, because vector sv1 was previously instantiated as having attributes of type String (line 168), the compiler is able to determine whether vector sv1 contains attributes that are compatible with the String variable s. Additionally, a cast instruction is not required to explicitly convert from a less specific type to a more specific type.
At line 178 the element at location 0 of vector sv2 is set equal to the String "one" and at line 180, a string variable s2 is set equal to the element (String) at location 0 in vector sv2, without the use of a cast instruction.
At line 182, an attempt is made to assign an element of a vector (sv1) that is of type String, to a variable (c2) that is of type Character. By including a parameter with each vector instantiation (as required by the class definition in lines 130-154), the compiler can determine without an explicit type cast, the element type of each vector instance. In knowing the type of element that is associated with a particular vector instance, the compiler can perform static type-checking to determine whether a variable type is compatible with the element type contained by the particular vector instance.
For example, by including the parameter "Character" in the instantiation of the vector cv at line 160, the compiler knows from that point forward that the elements of the vector cv are of type Character. This allows the compiler to perform static type-checking on all assignments involving elements of the vector cv. Thus, static type-checking provides the benefit of being able to identify incompatible type assignments at compile time, rather than at runtime. For example, the benefit of using static type checking is illustrated by line 182 where an attempt is made to assign an element of the vector sv1, that has been previously defined (instantiated) as type String (line 168), to a variable "c2", that is of type Character.
Because incompatible type assignment errors can be caught at compile time, the use of parameterized classes can significantly reduce the number of runtime errors caused by incompatible type casts. In addition, because the assigned element type for a particular class instance can be determined at compile time, the programmer is no longer required to write code that casts when extracting an element from a particular class instance.
Although parameterized class types provide the added benefit of allowing static type checking, an enormous amount of library code has been developed and installed that pre-dates the use of parameterized class types (i.e. created using unparameterized library code). Thus, a large investment, in terms of dollars and manpower has been made in developing unparameterized library code. In certain cases, the unparameterized library code has been distributed and is in use throughout the world. For example, an enormous amount of class code has been developed using the Java.TM. programming language that pre-dates the use of parameterized class types. This unparameterized class code has been compiled into class library byte code which has been distributed, and is currently in use, throughout the world.
As shown above, unparameterized class code has the disadvantage that it does not allow a compiler to perform static type-checking and requires the programmer to insert explicit type-casting instructions into the unparameterized user program source code. Thus, much of the existing unparameterized class libraries would have been easier to interface and develop class code with if parameterization had been available when class libraries were first developed.
One approach to generating "new" user program byte code, while still taking advantage of parameterized classes, is to convert parameterized code to unparameterized code using a heterogeneous translation. A heterogeneous translation is a translation that causes a different class to be generated for every parameter value used with the parameterized class. The heterogeneous translation method is in common use by such languages as C++, in which a form of macro expansion is used to create an instance of a new class type for each class type parameter.
For example, performing a heterogeneous translation on the parameterized class code previously shown in lines 130-154 and 160-182, the following classes will be generated for the different class parameter values (i.e. Character and String).
______________________________________ 200 class VectorCharacter { 202 public static final int CAPACITY = 4; 204 private Character [] oa = new Character[CAPACITY]; 208 public Character get (int i) { 210 if (0 &lt;= i && i &lt; CAPACITY) return oa[i]; 212 else throw new IndexOutOfBoundsException(); 214 } 216 public void set (int i, Character val) { 218 if(0&lt;= i && i &lt; CAPACITY) oa[i] = val; 220 else throw new IndexOutOfBoundsException(); 222 } 224 } 230 class VectorString { 232 public static final int CAPACITY = 4; 234 private String [] oa = new String[CAPACITY]; 238 public String get (int i) { 240 if (0 &lt;= i && i &lt; CAPACITY) return oa[i]; 242 else throw new IndexOutOfBoundsException(); 244 } 246 public void set (int i, String val) { 248 if(0 &lt;= i && i &lt; CAPACITY) oa[i] = val; 250 else throw new IndexOutOfBoundsException(); 252 } 254 } ______________________________________
FIG. 1 illustrates a block diagram in which the heterogeneous translation is used to generate "new" class files while taking advantage of parameterized class code. FIG. 1 is described in terms of the previous Vector class code examples. As depicted in FIG. 1, class files 102 consists of unparameterized user program byte code 106 and unparameterized class library byte code 104. The unparameterized class library byte code 104 was generated by compiling 110 unparameterized class library source code 116 (code lines 70-94) to produce a Vector of Object. The unparameterized user program byte code 106 was generated by compiling 108 unparameterized user program source code 112 (code lines 102-124) with unparameterized class definitions 114 and is used to invoke methods in the Vector of Object. The unparameterized class definitions 114 provide compile time interface definitions for interfacing the unparameterized user program source code 112 with the unparameterized class library byte code 104. As depicted by double arrow 130, the unparameterized user program byte code 106 is compatible with and therefore can interface with the unparameterized class library byte code 104.
Parameterized user program source code 126 represents program code (code lines 160-182) which was developed with the use of parameters (Character and String). Parameterized class definition 128 provides interface definitions for interfacing the parameterized user program source code 126 with unparameterized class library byte code 104. In generating user program byte code 118, static type-checking 124 is performed on the parameterized user program source code 126 and parameterized class definitions 128. As previously discussed, static type checking is performed on the parameterized source code to determine if the code contains any incompatible type assignments. After the static checking 124 is performed, a heterogeneous translation 122 is performed to create a class instance for each class type parameter used in the parameterized user program source code 126 (i.e. line 200-224 and 230-254). Thus, referring to the previous code examples, all vector instances having elements of type "Object" are translated into vector instances having elements of the particular class type parameter. For example, the code at line 160 above using the heterogeneous translation method, will create an instance of a vector of type Character (lines 200-224) and the code at line 168 and 176, will create an instance of a vector of type String (lines 230-254). The output from the heterogeneous translation 122 is then compiled 120 into user program byte code 118, which invokes methods of Vector of Character and Vector of String.
A drawback associated with using the heterogeneous translation method to generate user program byte code is that the byte code created from the parameterized types is of a different form than the byte code that was originally generated using the unparameterized class libraries. Specifically, using the heterogeneous translation method, the newly created byte code contains additional references to classes for each element type as specified by each parameter type (i.e. Character, String). However, the byte code that is compiled from the unparameterized class files do not contain these additional class references. These additional references cause the byte code that is created from the parameterized class files to be incompatible with byte code that was produced from unparameterized class files on existing systems that are currently in use. These systems that execute byte code are generally termed "code executors".
For example, an enormous investment has been made in the development of code executors such as the Java Virtual Machines (JVMs). The JVMs interpret the byte code to create objects which are instances of the classes defined by the class definitions. These objects control the execution of the JVMs. JVMs are described in detail in The Java Virtual Machine Specification (1996), authored by Tim Lindholm & Frank Yellin. Because the JVMs expect the byte code to contain classes of a particular type (e.g. Object), the byte code produced using the heterogeneous translation method is incompatible and can not be correctly interpreted by the JVMs. Thus, these JVMs cannot take advantage of parameterizing the unparameterized class libraries using the heterogeneous translation method.
Based on the foregoing, it is highly desirable to develop a mechanism that provides for the benefits of using parameterized code (e.g. catching errors at compile time, avoiding the need for explicit type casting) but still allows for the use of old unparameterized class libraries and old virtual machines that don't support parameterized code.